#include <cstdio>
#include <cstdlib>
#include <vector>
using namespace std;

#define NMAX 1005
#define MMAX 10005

// a type of 'true' indicates an 'L' edge, that is, the two
// relevant cows should be of different type
struct edge {
    int dest;
    bool type;
    int index;
};

vector<edge> edges[NMAX];
int components[NMAX];
bool type[NMAX];

// DFS flood-fill, restricting to edges with indices at most
// nstatments
bool dfs(int v, int comp, bool t, int nstatements) {
    if (components[v] != 0) {
        return t == type[v];
    }

    components[v] = comp;
    type[v] = t;

    for (int i = 0; i < edges[v].size(); i++) {
        if (edges[v][i].index < nstatements &&
            !dfs(edges[v][i].dest, comp, edges[v][i].type ^ t, nstatements)) {
            return false;
        }
    }

    return true;
}

// Returns true if the first nstatements statements are consistent
bool consistent(int n, int nstatements) {
    for (int i = 0; i < n; i++) {
        components[i] = 0;
    }
    int nComponents = 0;
    for (int i = 0; i < n; i++) {
        if (components[i] == 0) {
            nComponents++;
            if (!dfs(i, nComponents, false, nstatements)) {
                return false;
            }
        }
    }
    return true;
}

int main() {
    freopen("truth.txt","r",stdin);
    //freopen("truth.out","w",stdout);

    int n, m;
    scanf("%d", &n);
    scanf("%d", &m);

    for (int line = 0; line < m; line++) {
        int a, b;
        char c;
        scanf("%d", &a);
        scanf("%d", &b);
        a--;
        b--;
        do {
            c = fgetc(stdin);
        } while (c != 'L' && c != 'T');

        edge e;
        e.type = (c == 'L');
        e.index = line;

        e.dest = b;
        edges[a].push_back(e);
        e.dest = a;
        edges[b].push_back(e);
    }

    // binary search
    // invariant: lo <= answer < hi
    int lo = 1, hi = m+1;
    while (lo + 1 < hi) {
        int mid = (lo + hi) / 2;
        if (consistent(n, mid)) {
            lo = mid;
        } else {
            hi = mid;
        }
    }

    printf("%d\n", lo);
}
